package org;

import java.util.List;

/**
 * 数字预测
 * 
 * <pre>
 * a[3 ^ n][0] = a[0][0] + a[0][3 ^ n]
 * </pre>
 * 
 * @author zhujunbing
 * @date 2019年5月10日
 */
public class DigitalPredictor {
	private static Integer total = 1 + 2 + 3;

	public static void main(String[] args) {

		int a = 1024 * 1024;
		;

		// 求 a的 3进制

		// int a = 14;
		three(a);
		int size = a;
		System.out.println("size:" + size);
		int[] arr = new int[size];
		while (size-- != 0) {
			int random = 1 + (int) (Math.random() * 3);
			arr[size] = random;
			// System.out.println(size+" "+random );
		}
		//
		// int [] arr = {3,1,3,2,1};

		long currentTimeMillis = System.currentTimeMillis();
		// System.out.println(arr[0]==arr[3]?arr[0]:arr[0]^arr[3]);
		// my2(arr, a);
		int my3 = my3(arr);

		System.out.println("耗时" + (System.currentTimeMillis() - currentTimeMillis) + "ms");
		System.out.println(my3);
		// System.out.println("topValue = " + arr[0]);

	}

	private static void three(int number) {
		int sys = 3;
		int arr[] = new int[50];
		int count = 0;
		number--;
		while (number != 0) {
			arr[count++] = number % sys;
			number = number / sys;
		}
		System.out.print("size-1的3进制");
		while (--count >= 0) {
			System.out.print(arr[count]);
		}
		System.out.println();
	}

	public static Integer upValue(Integer a, Integer b) {
		return a == b ? a : total - a - b;
	}

	/**
	 * 这个是给我题目的人写的
	 * 
	 * @param list
	 * @return
	 * @date 2019年5月10日
	 */
	public static List<Integer> findUpList(List<Integer> list) {
		// System.out.println(list);
		if (list.size() == 1) {
			return list;
		}

		for (int i = 0; i < list.size() - 1; i++) {
			list.set(i, upValue(list.get(i), list.get(i + 1)));
		}
		list.remove(list.size() - 1);
		return findUpList(list);
	}

	/**
	 * 这个是直接计算
	 * 
	 * @param array
	 * @date 2019年5月10日
	 */
	public static void my1(int[] array) {

		for (int i = array.length; i > 0; i--) {

			for (int j = 0; j < i - 1; j++) {

				if (array[j] != array[j + 1]) {
					array[j] = array[j] ^ array[j + 1];
				}

			}
		}
	};

	// 31321
	// 2213
	// 232
	// 11
	// 1
	/**
	 * a[3^n][i]=a[0][i]#a[0][i+3^n]
	 * 
	 * @param array
	 * @date 2019年5月10日
	 */
	public static void my2(int[] array, int length) {

		if (length < 4) {

			for (int i = length; i > 0; i--) {

				for (int j = 0; j < i - 1; j++) {

					if (array[j] != array[j + 1]) {
						array[j] = array[j] ^ array[j + 1];
					}

				}
			}

			System.out.println("最后" + length + "层结束");
			return;
		}

		int base = 1;
		int temp = length - 1;
		while (temp / 3 >= 1) {
			base *= 3;
			temp /= 3;
		}
		System.out.println("升高了" + base + "层");

		// 需要计算
		for (int i = 0; i <= length - 1 - base; i++) {
			// System.out.println(i);
			array[i] = array[0] == array[base + i] ? array[0] : array[0] ^ array[base + i];
		}

		my2(array, length - base);

		System.out.println("");
	}

	/**
	 * 1 1=1 1 2=3 1 3=2
	 * 
	 * @param a
	 * @param b
	 * @return
	 * @date 2019年5月23日
	 */
	private static int func(int a, int b) {
		return a == b ? a : a ^ b;
	}

	/**
	 * 还可以优化 a[3^n+k][i]=a[k][i]#a[k][3^n+i]
	 * 
	 * @param array
	 * @param length
	 * @date 2019年5月22日
	 */
	public static int my3(int[] array) {
		// TODO 可以发现，需要计算的其实不需要那么多，
		// 以16size举例
		// 15的3进制 120
		// 例如 a[15][0] = a[12][0]+a[12][3]=(a[9][0]+a[9][3])+(a[9][3]+a[9][6])
		// 只需要计算1+2+3=6次 1+1*2
		// a[15][0] = a[6][0]+a[6][9] = (a[3][0]+a[3][6])+(a[3][9]+a[3][12]) 需要1+2+4=7次
		// 每次进行3^n步长的跳跃时，需要计算的点最多*2

		int[] step = new int[50];
		int deep = 0;
		int length = array.length;
		if (length == 1) {
			return array[0];
		}
		while (length > 1) {
			int base = 1;
			int temp = length - 1;
			while (temp / 3 >= 1) {
				base *= 3;
				temp /= 3;
			}
			step[deep] = base;
			deep++;
			length -= base;
		}

		return fx(array.length - 1, 0, array, step, deep);
	}

	/**
	 * 
	 * @param r
	 * @param c
	 * @param arr
	 * @param step
	 * @param deep	
	 * @return	
	 */
	private static int fx(int r, int c, int[] arr, int[] step, int deep) {
		if (r == 0) {
			return arr[c];
		} else {
			return func(fx(r - step[deep], c, arr, step, deep - 1),
					fx(r - step[deep], c + step[deep], arr, step, deep - 1));
		}

	}

}
